Various computer graphics applications call for modeling objects. This modeling may be done for purposes such as computation and rendering, and numerical analysis using the finite element analysis method. A solid object is conveniently modeled by creating a mesh of points having a geometry corresponding with that of the object being modeled. Many applications require that an object being modeled, having an arbitrary shape, be modeled by decomposing the object into a set of simple elements such as tetrahedra. For each tetrahedron, a calculation is made to determine a physical attribute of the object, under a predetermined condition. The physical attribute could be shading, vibrational displacement responsive to a predetermined forcing function, a temperature gradient, etc. Then, the graphic representation of the object as a whole is shaded or deformed, using the calculated values for the tetrahedra.
Each element is made up of vertices (nodes), edges, and faces, and each element defines a region enclosed within its faces. In a mesh, there are predefined rules about how two elements may be geometrically connected. For instance it might be required that any two elements be either disjoint, or share one or more vertices. Alternatively, it might be required that any two elements share a whole face, edge, vertex, or nothing. Such rules have been referred to as a "geometric complex" in Hocking et al., "Topology", Mineola, N.Y.: Dover Publications, Inc. (1988), pp. 199-206. Hocking et al. defined a geometric complex as a collection of properly joined geometric simplices, wherein, for each geometric simplex which belongs to the geometric complex, every face of that geometric simplex also belongs to the geometric complex. Simplices are "properly joined" if their intersection is either the empty set or a subsimplex of each of the simplices.
Geometric simplices are defined for various numbers of dimensions. A geometric 0-simplex is a single point, a geometric 1-simplex is a closed line segment, a geometric 2-simplex is a closed triangular plane region, a geometric 3-simplex is a solid tetrahedron, and so on. The present invention is primarily concerned with three-dimensional modeling of arbitrarily shaped objects as a geometric complex. Geometric 3-simplices, i.e., tetrahedra, are thus properly joined if they have a face in common.
Some applications allow an object to be modeled by a mesh including different elements, such as tetrahedra, pentahedra, and hexahedra. Other applications require that only a single type of element, such as only tetrahedra, be used. Different criteria determine the desirable form a mesh should take. A balanced mixture of different elements might be desirable due to technical reasons, such as providing better system performance, or to human preference, for easier visualization of the results. If an object includes several components, or has portions made of different materials, then it is required that the boundaries of the elements of the mesh representation conform to the boundaries between the components or portions. In many applications, the total number of elements making up the mesh should preferably be as small as possible.
Therefore, the problem of how to model an arbitrarily shaped object with a mesh to optimize visual appearance and system performance, minimize the total number of elements, or achieve other desired results, is a challenge which faces systems designers.
Conventional systems and methods have focused on decomposing an object into only tetrahedra. For instance U.S. Pat. No. 5,010,501, issued to Arakawa and titled "Three-Dimensional Geometry Processing Method and Apparatus Therefor", discloses a method in which a grid, defined by planes perpendicular to the coordinate axes, is superimposed on a geometric region. See, for instance FIG. 3(b) of Arakawa. Elements defined by the grid are then dissected into tetrahedra. The Arakawa method has several disadvantages. First, because of the imposed grid, the number of tetrahedra produced is likely to be very large, while it would be preferable to keep the number as small as possible. Second, because of the imposed grid, the resulting tetrahedra probably will not follow the natural shape and contour of the geometric region. Also, the method does not handle curved surfaces well, and is well-suited only for 2.5 dimensional regions, that is, regions such as prisms or cut-outs from a sheet of finite thickness material, which do not vary in one direction.
Another method is taught in U.S. Pat. No. 3,889,107, issued to Sutherland and titled "System of Polygon Sorting by Dissection." In the Sutherland method, a region, defined by a polygonal surface, is dissected by dissection planes which intersect the edges of the polygons making up the surface. Thus, the dissection follows the form of the region (to a degree), rather than following an imposed coordinate axis. However, the Sutherland method also has drawbacks. It does not handle regions with curved surfaces well, and may also produce an undesirably large number of pieces. In addition, a small change to the geometry produces global changes in the decomposition. That is, a small change to the shape of one face causes the dissection plane for an edge of the face to move, and change the decomposition throughout the region.
Still another approach was made, in part, by the present inventor in U.S. Pat. No. 4,933,889, titled "Method for Fine Decomposition in Finite Element Mesh Generation." In this method, a domain represented by a polygonal boundary is divided into elements which generally correspond with Voronoi regions, that is, regions which are closer to respective ones of the polygonal line segments or reflex vertices between line segments. Symmetric axes are used as the basis for decomposition. As shown in the drawings of the '889 patent, this method is an improvement over other conventional systems in that the elements more closely follow the natural shape and contour of the polygonal surface of the region. However, this patent does not address the problem of three-dimensional decomposition.
Cavendish et al., "An Approach to Automatic Three-Dimensional Finite Element Mesh Generation", International Journal for Numerical Methods in Engineering, Vol. 21, pp. 329-347 (1985) describes a method for generating a mesh by inserting node points within and on the boundary of the structure to be meshed, and triangulating the node points to form a network of well-proportioned elements.
For finite element analysis, any tetrahedron should fall either totally within or totally outside of the body. If a tetrahedron crosses a boundary of the body, it must be subdivided into two or more tetrahedra which meet this requirement. Thus, the first step of the Cavendish method is employed.
To accomplish the latter step, Delaunay triangulation and/or tetrahedrization is used. The Delaunay method involves creating a tetrahedral mesh representation of a body such that, if a circumsphere is defined to contain any given one of the tetrahedra (i.e., the four vertices of the tetrahedron are on the surface of the circumsphere), no mesh points fall within the circumsphere's volume. As a consequence, the elements (triangles or tetrahedra) tend to be well-proportioned.
However, the Cavendish method is likely to produce a mesh having an undesirably large number of elements, and it does not address how the number of elements can be reduced.
The present inventor also contributed to the invention of U.S. Pat. No. 5,125,038, titled "Face and Edge Trim Method for An Automatic Mesh Generation System". This method produces a mesh of tetrahedra according to the Delaunay method. The '038 patent teaches a method for meeting this requirement by producing an initial mesh, adding a vertex point on any body edge which does not coincide with an edge of one of the finite elements (i.e., tetrahedra) making up the mesh, and creating additional finite elements by adding edges between the new vertex point and nearby vertices. The method of the '038 patent also includes locating a finite element having a first edge coincident with a body edge and a second edge passing through a face of the body, placing a new vertex point on the body face in the vicinity of the second edge of the finite element, so as to minimize the number of added required vertices, and creating new finite elements by adding edges between this new vertex point and nearby vertices.
Thus, it will be seen that the '038 patent advantageously produces a three-dimensional mesh which more closely follows the natural shape and contour of the body, and is fully three-dimensional. However, it would be desirable to decrease the total number of finite elements making up a mesh representation of a body, while maintaining the advantages of the method of the '038 patent.